#!/usr/bin/python

from sage.graphs.graph import *

evil_dict = {}

class String:
    def __init__(self, s):
        self.string = s
    def __repr__(self):
        return self.string.__repr__()

def count_change(amount):
    global evil_dict
    evil_dict = {}
    return cc(amount, 5)

def cc(amount, kinds_of_coins):
    if amount == 0:
        evil_dict['(cc 0 %d)' % kinds_of_coins] = [String(1)]
        return 1
    elif amount < 0 or kinds_of_coins == 0:
        evil_dict['(cc %d %d)' % (amount, kinds_of_coins)] = [String(0)]
        return 0
    else:
        evil_dict['(cc %d %d)' % (amount, kinds_of_coins)] = ['(cc %d %d)' %
                (amount, kinds_of_coins - 1),
                '(cc %d %d)' % (amount - first_denomination(kinds_of_coins),
                    kinds_of_coins)]
        return cc(amount, kinds_of_coins - 1) +\
                cc(amount - first_denomination(kinds_of_coins),
                        kinds_of_coins)

def first_denomination(kinds_of_coins):
    d = { 1: 1, 2: 5, 3: 10, 4: 25, 5: 50}
    return d[kinds_of_coins] # if something goes wrong, it's better to raise
                             # an exception...

count_change(11)
evil_dict['(count-change 11)'] = '(cc 11 5)'
G = DiGraph(evil_dict)
G.plot().show()

#
# Believe it or not, evil_dict is a tree.
#

